/*
 * Copyright (c) 2022 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
 
class AccessFannkuchConst {
    public static final int CURRENT_LOOP_COUNT = 30;
    public static final int MAX_LOOP_COUNT = 80;
    public static final int MS_CONVERSION_RATIO = 1000000;
}

class AccessFannkuch  {
    public static int fannkuch(int n) {
        // System.out.println("method fannkuch was called");
        int check = 0;
        int[] perm = new int[n];
        int[] perm1 = new int[n];
        int[] count = new int[n];
        int[] maxPerm = new int[n];
        int maxFlipsCount = 0;
        int m = n - 1;

        // System.out.println("method fannkuch, Before the loop starts, maxFlipsCount's value is ->" + maxFlipsCount);
        for (int i = 0; i < n; i++) {
            perm1[i] = i;
        }
        int r = n;
        while (true) {
            if (check < AccessFannkuchConst.CURRENT_LOOP_COUNT) {
                String s = "";
                for (int i = 0; i < n; i++) {
                    s += perm1[i] + 1;
                    check += 1;
                }
            }
            while (r != 1) {
                count[r - 1] = r;
                r -= 1;
            }

            if (!(perm1[0] == 0 || perm1[m] == m)) {
                for (int i = 0; i < n; i++) {
                    perm[i] = perm1[i];
                }

                int flipsCount = 0;
                int k = 0;

                while (!(perm[0] == 0)) {
                    k = perm[0];
                    int k2 = (k + 1) >> 1;
                    for (int i = 0; i < k2; i++) {
                        int temp = perm[i];
                        perm[i] = perm[k - i];
                        perm[k - i] = temp;
                    }
                    flipsCount += 1;
                }

                if (flipsCount > maxFlipsCount) {
                    maxFlipsCount = flipsCount;
                    for (int i = 0; i < n; i++) {
                        maxPerm[i] = perm1[i];
                    }
                }
            }

            while (true) {
                if (r == n) {
                    return maxFlipsCount;
                }
                int perm0 = perm1[0];
                int i = 0;
                while (i < r) {
                    int j = i + 1;
                    perm1[i] = perm1[j];
                    i = j;
                }
                perm1[r] = perm0;

                count[r] = count[r] - 1;
                if (count[r] > 0) {
                    break;
                }
                r += 1;
            }
        }
    }
}

interface ArkTools {
    int timeInUs(int args);
}

/*
 * @State
 * @Tags Jetstream2
 */
class Benchmark {
    public static void main(String[] args) {
        Benchmark benchmark = new Benchmark();
        benchmark.runIterationTime();
    }

    public void run() {
        int n = 8;
        int ret = AccessFannkuch.fannkuch(n);
        // System.out.println("After method a is called, ret's value is ->" + ret);
        int expected = 22;
        if (ret != expected) {
            System.err.println("ERROR: bad result: expected " + expected + " but got " + ret);
        }
    }

    /*
   * @Benchmark
   */
    public void runIterationTime() {
        long start = System.nanoTime();
        for (int i = 0; i < AccessFannkuchConst.MAX_LOOP_COUNT; i++) {
            this.run();
        }
        long end = System.nanoTime();
        System.out.println("access-fannkuch: ms = " + (double)(end - start) / AccessFannkuchConst.MS_CONVERSION_RATIO);
    }
}

